java递归ConcurrentHashMap。ComputeFabSent()调用永远不会终止。Bug还是“功能”?
不久前,I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively,使用ConcurrentHashMap
缓存和新的、有用的computeIfAbsent()
方法:
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class Test {
static Map<Integer, Integer> cache = new ConcurrentHashMap<>();
public static void main(String[] args) {
System.out.println(
"f(" + 8 + ") = " + fibonacci(8));
}
static int fibonacci(int i) {
if (i == 0)
return i;
if (i == 1)
return 1;
return cache.computeIfAbsent(i, (key) -> {
System.out.println(
"Slow calculation of " + key);
return fibonacci(i - 2) + fibonacci(i - 1);
});
}
}
我之所以选择ConcurrentHashMap
,是因为我想通过引入并行性(我最后没有这么做),使这个例子更加复杂
现在,让我们将数字从8
增加到25
,并观察发生了什么:
System.out.println(
"f(" + 25 + ") = " + fibonacci(25));
这个项目从未停止过。在方法内部,有一个循环永远运行:
for (Node<K,V>[] tab = table;;) {
// ...
}
我用的是:
C:\Users\Lukas>java -version
java version "1.8.0_40-ea"
Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23)
Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)
Matthias, a reader of that blog post also confirmed the issue (he actually found it)
这很奇怪。我本以为会出现以下两种情况:
- 它起作用了
- 它抛出一个
ConcurrentModificationException
但就是永不停歇?这似乎很危险。是虫子吗?还是我误解了合同
# 1 楼答案
这当然是一个“功能”。Javadoc的^{} 内容如下:
“不得”的措辞是一个明确的约定,我的算法违反了这个约定,尽管出于相同的并发原因
仍然有趣的是没有
ConcurrentModificationException
。相反,这个程序永远不会停止——在我看来,这仍然是一个相当危险的错误(即infinite loops. or: anything that can possibly go wrong, does)注:
^{} 或^{} Javadoc并不禁止这种递归计算,这当然是荒谬的,因为缓存的类型是
Map<Integer, Integer>
,而不是ConcurrentHashMap<Integer, Integer>
。对于子类型来说,彻底地重新定义超级类型契约是非常危险的(Set
与SortedSet
是问候语)<因此,在超级类型中也应该禁止执行这种递归# 2 楼答案
这在JDK-8062841中是固定的
在2011 proposal中,我在代码审查期间发现了这个问题。JavaDoc已更新,并添加了临时修复程序。由于性能问题,它在进一步重写时被删除
在2014 discussion中,我们探索了更好地检测和失败的方法。请注意,为了考虑低级别的更改,一些讨论被脱机到私人电子邮件。虽然不是每个案例都可以涵盖,但普通案例不会被活锁。这些fixes在Doug的存储库中,但还没有发布到JDK版本中
# 3 楼答案
这与bug非常相似。 因为,如果你用32的容量创建缓存,你的程序将一直工作到49。 有趣的是,参数sizeCtl=32+(32>;>;>;1)+1)=49! 可能是调整尺寸的原因